﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0148_FractionToDecimal : IAlgorithm
    {
        // 分数到小数

        // 给定两个整数，分别表示分数的分子 numerator 和分母 denominator，以 字符串形式返回小数 。
        // 如果小数部分为循环小数，则将循环的部分括在括号内。
        // 如果存在多个答案，只需返回 任意一个 。
        // 对于所有给定的输入，保证 答案字符串的长度小于 10^4 。

        // 提示：
        //  -2^31 <= numerator, denominator <= 2^31 - 1
        //  denominator != 0

        public void Test()
        {
            //Console.WriteLine(Algorithm());
        }

        // 算法
        public string FractionToDecimal(int numerator, int denominator)
        {
            long numeratorLong = (long)numerator;
            long denominatorLong = (long)denominator;
            if (numeratorLong % denominatorLong == 0)
            {
                return (numeratorLong / denominatorLong).ToString();
            }

            StringBuilder sb = new StringBuilder();
            if (numeratorLong < 0 ^ denominatorLong < 0)
                sb.Append('-');

            // 整数部分
            numeratorLong = Math.Abs(numeratorLong);
            denominatorLong = Math.Abs(denominatorLong);
            long integerPart = numeratorLong / denominatorLong;
            sb.Append(integerPart);
            sb.Append('.');

            // 小数部分
            var fractionPart = new StringBuilder();
            var remainderIndexMap = new Dictionary<long, int>();
            long remainder = numeratorLong % denominatorLong;
            int index = 0;
            while (remainder != 0 && !remainderIndexMap.ContainsKey(remainder))
            {
                remainderIndexMap.Add(remainder, index);
                remainder *= 10;
                fractionPart.Append(remainder / denominatorLong);
                remainder %= denominatorLong;
                index++;
            }
            if (remainder != 0)
            { // 有循环节
                int insertIndex = remainderIndexMap[remainder];
                fractionPart.Insert(insertIndex, '(');
                fractionPart.Append(')');
            }
            sb.Append(fractionPart.ToString());

            return sb.ToString();
        }
    }
}
